# LeetCode 210. 课程表 II
# https://leetcode.cn/problems/course-schedule-ii/
import collections
from typing import List


# DFS
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        WHITE, GRAY, BLACK = 0, 1, 2
        colors = [WHITE] * numCourses
        stack = []
        edges = collections.defaultdict(list)
        for info in prerequisites:
            edges[info[1]].append(info[0])

        def dfs(u):
            colors[u] = GRAY
            for v in edges[u]:
                if colors[v] == WHITE:
                    dfs(v)
                elif colors[v] == GRAY:
                    raise RuntimeError
            colors[u] = BLACK
            stack.append(u)

        for i in range(numCourses):
            if colors[i] == WHITE:
                try:
                    dfs(i)
                except:
                    return []
        stack.reverse()
        return stack


# 拓扑排序
class Solution2:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        result = []
        adj = [[] for i in range(numCourses)]
        in_degree = {i: len(adj[i]) for i in range(numCourses)}
        for prerequest in prerequisites:
            course0, course1 = prerequest
            adj[course1].append(course0)
            in_degree[course0] += 1

        nodes = [i for i in range(numCourses) if in_degree[i] == 0]
        while nodes:
            node = nodes.pop()
            result.append(node)
            for v in adj[node]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    nodes.append(v)
        if len(result) != numCourses:
            result = []
        return result


if __name__ == '__main__':
    numCourses = 2
    prerequisites = [[1, 0]]
    numCourses = 4
    prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
    # numCourses = 3
    # prerequisites = [[1,0],[1,2],[0,1]]
    print(Solution().findOrder(numCourses, prerequisites))
    print(Solution2().findOrder(numCourses, prerequisites))
